/**
 * 数组结构转树形结构
 * @param {*} rawArr 数组
 * @param {*} fieldNames 可定制的字段名
 * @param {*} fieldNames.id id id字段名
 * @param {*} fieldNames.parentId parentId 父节点id字段名
 * @param {*} fieldNames.childen childen childen字段名
 *
 * @example
 * let arr = [
 *  { _id: '123', parent: null, name: '123' },
 *  { _id: '456', parent: '123', name: '456' },
 *  { _id: '567', parent: '456', name: '567' },
 *  { _id: '789', parent: '123', name: '789' }
 * ]
 * let tree = arrToTree(arr, { id: '_id', parentId: 'parent' });
 */
function arrToTree(rawArr, fieldNames = {}) {
  let {
    id: idField = 'id',
    parentId: parentIdField = 'parentId',
    childen: childenField = 'children'
  } = fieldNames;
  let arr = JSON.parse(JSON.stringify(rawArr));

  let tree = [],
    ids = new Set(),
    parentChildrenMap = {};

  arr.forEach(item => {
    if (!item[idField]) {
      return;
    }
    ids.add(item[idField]);
    if (!parentChildrenMap[item[parentIdField]]) {
      parentChildrenMap[item[parentIdField]] = [];
    }
    parentChildrenMap[item[parentIdField]].push(item);
  });
  let currentLevels = [],
    maxIters = arr.length;
  arr.forEach(item => {
    if (!ids.has(item[parentIdField])) {
      tree.push(item);
      currentLevels.push(item);
    }
  });
  let iteredIds = new Set();
  while (currentLevels.length && maxIters) {
    let current = currentLevels.shift();
    iteredIds.add(current[idField]);
    let childenList = (parentChildrenMap[current[idField]] || []).filter(
      // 防止循环引用
      item => !iteredIds.has(item[idField])
    );
    if (childenList.length) {
      current[childenField] = childenList;
      currentLevels.push(...childenList);
    }
    maxIters--;
  }

  return tree;
}

export default arrToTree;
